package com.kevin.Code.Backtrack;

import com.kevin.Code.Array.Permutationsii;

import java.util.*;

/**
 * @author Vinlee Xiao
 * @Classname permutationsii
 * @Description Leetcode 47. 全排列 II 中等难度 回溯算法  有点难度
 * @Date 2021/9/23 11:24
 * @Version 1.0
 */
public class permutationsii {

    List<List<Integer>> res = new ArrayList<>();
    boolean[] visited;
    /**
     *
     * @param nums
     * @return
     */
//    public List<List<Integer>> permuteUnique(int[] nums) {
//
//        List<Integer> combiner = new LinkedList<>();
//
//        List<Integer> index = new LinkedList<>();
//
//        dfs(nums,combiner,index);
//
//        return res;
//
//    }


//    public void dfs(int[] nums, List<Integer> combine, List<Integer> index) {
//
//        if (nums.length == combine.size()) {
//
//            res.add(new LinkedList<>(combine));
//        }
//
//        for (int i = 0; i < nums.length; i++) {
//            if (!index.contains(i)) {
//                combine.add(nums[i]);
//                index.add(i);
//                dfs(nums, combine, index);
//                combine.remove(combine.size() - 1);
//                index.remove(index.size() - 1);
//            }
//
//        }
//
//    }

    /**
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {

        List<Integer> combiner = new LinkedList<>();
        visited = new boolean[nums.length];
        //进行排序
        Arrays.sort(nums);

        dfs(nums, combiner, 0);

        return res;
    }


    /**
     * @param nums
     * @param combiner
     * @param index
     */
    public void dfs(int[] nums, List<Integer> combiner, int index) {

        if (nums.length == index) {
            res.add(new LinkedList<>(combiner));
        }

        for (int i = 0; i < nums.length; i++) {

            //控制语句
            //比较难以理解 确保每次放入index位置的数
            if (visited[i] || (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1])) {
                continue;

            }

            combiner.add(nums[i]);
            visited[i] = true;
            dfs(nums, combiner, index + 1);
            visited[i] = false;
            combiner.remove(index);

        }
    }


    public static void main(String[] args) {

        int[] nums = new int[]{1, 2, 3};
        permutationsii permutationsii = new permutationsii();
        List<List<Integer>> lists = permutationsii.permuteUnique(nums);


        for (List<Integer> list : lists) {
            for (Integer e : list) {
                System.out.print(e);
            }
            System.out.println("---------");
        }
    }
}
